package Sort2;

import java.util.Arrays;

public class Sort {
    public static void main(String[] args) {
        int[] arr = new int[]{1,3,5,2,4,6};
        merge(arr,0,5);
        System.out.println(Arrays.toString(arr));
    }
    public static void main1(String[] args) {
        int[] arr = new int[]{1,3,5,2,4,6};
        q(arr,0,5);
        System.out.println(Arrays.toString(arr));
    }
    public static void q(int[] q,int l,int r){
        if(l >= r) return;
        int x = q[l+r>>1];
        int i = l - 1;
        int j = r + 1;
        while (i < j){
            do i++;while (q[i] < x);
            do j--;while (q[j] > x);
            if(i < j){
                int temp = q[i];
                q[i] = q[j];
                q[j] = temp;
            }
        }
        q(q,l,j);
        q(q,j+1,r);
    }
    public static void merge(int[] q,int l,int r){
        if (l >= r) return;
        int m = l+r>>1;
        merge(q,l,m);
        merge(q,m+1,r);
        int[] temp = new int[r-l+1];
        int i = l;
        int j = m+1;
        int k = 0;
        while (i <= m && j <= r){
            if(q[i] < q[j]) temp[k++] = q[i++];
            else temp[k++] = q[j++];
        }
        while (i <= m) temp[k++] = q[i++];
        while (j <= r) temp[k++] = q[j++];
        for (i = l,j = 0;i<=r;i++,j++){
            q[i] = temp[j];
        }
    }
    public static void maopao(int[] arr){
        for(int i = 0;i<arr.length;i++){
            for(int j =0;j<arr.length-i-1;j++){
                if(arr[j] < arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}
